package org.kfive.nova.algorithm;

import com.google.common.collect.Lists;

import java.util.List;

/*
* MaxSubSum.java
* Created  by  lizhanwu
* Created on 2016-6-13 14:28
*/
public class MaxSubSum {

    public static List<Integer> maxSubSum(List<Integer> numList){
        List<Integer> subList = Lists.newArrayList();
        if(numList==null || numList.size()<=0){
            return subList;
        }
        Integer sum = 0;
        Integer maxSum = 0;
        Integer maxStart = 0;
        Integer maxEnd = 0;
        Integer start = 0;
        Integer position = 0;
        for (Integer num : numList){
            sum += num;
            if(sum>maxSum){
                maxSum = sum;
                maxStart = start;
                maxEnd = position+1;
            }
            if(sum<0){
                sum = 0;
                start = position+1;
            }
            position++;
        }
        subList = numList.subList(maxStart,maxEnd);
        return subList;
    }

    public static void main(String[] args) {
        List<Integer> numList = Lists.newArrayList(5,-4,-2,2);
        System.out.println(MaxSubSum.maxSubSum(numList));
    }

}
